Laser distance-measuring systems measure space to such a high degree of measurement density that the resultant mass of points, often called a point cloud, can appear as a coherent scene in the manner of a pointillist painting. Systems meeting this description include the laser scanner described in U.S. Pat. No. 5,988,862, the disclosure of which is hereby incorporated by reference, the Leica HDS6000 laser scanner from Leica Geosystems HDS, LLC, of San Ramon, Calif., or other LIDAR systems—such as the airborne LIDAR system disclosed in U.S. patent application Ser. No. 11/397,246 filed Apr. 4, 2006, and incorporated herein by reference. Each of these systems produce point clouds or sets of echoes, which are data sets representing points whose position and distance are sensed by the system.
Typically, the systems collect data in such a way to transform raw sensor data into point data that have three position coordinates, x, y, and z. The raw sensor data is expressed in spherical coordinates: an angle θ that represents the angle of rotation about a vertical axis (shown as the z-axis in FIG. 4 of U.S. Pat. No. 5,988,862), an angle φ that represents the angle of rotation about a horizontal axis (shown as the y-axis in FIG. 4 of the '862 patent) and a range or distance ρ. The angle coordinates correspond with the movable laser-scanner or LIDAR components that determine the direction of an emitted laser pulse. These spherical coordinates are transformed into Cartesian coordinates, which are more convenient for later operations on the data. Once transformed, the z coordinate corresponds to the range ρ and represents the distance of a point from the laser scanner. (We have moved from defining the z-axis as shown in FIG. 4 of the '862 patent to the definition shown in FIG. 6A of that patent. We adhere to the definition of the x-, y-, and z-axes shown in FIG. 6A for the remainder of this specification, but one of ordinary skill will appreciate that the label attached to the Cartesian axes is arbitrary.) The aggregated z coordinates of points in a point cloud generally do not follow a predicable pattern. Indeed, the z coordinates of points are determined by the objects in the space that the laser system is measuring. In contrast, the x and y coordinates of points follow a pattern because the laser systems—whether a laser scanner or aerial LIDAR-collect data in a regular pattern.
But using the data from three-dimensional (“3D”) laser scanners is typically a time-consuming process. Current-generation laser scanners collect data at a rate much faster than the accompanying software can process it in real time. Some current laser scanners can collect data as fast as 500,000 data points per second. Near-term 3D imagers (based on grids of collectors similar to CCDs) may soon reach 30 million data points per second (30 Frames/sec at 1 K×1 K points=1 M points per frame).
This produces a lot of data. Typically a 3D data point will carry along somewhere between 14 to 30 bytes of data depending on the resolution of the device and the attributes associated with each point (e.g., 12 bytes for float precision points, 24 bytes for double precision points, 2 bytes for intensity return, 3 bytes for color). Consider a 14-byte-per-point baseline laser-scanner system. This system produces a data rate of roughly 7 MB/sec at a scan rate of 500 K points/sec. Given that disk write speeds are roughly 30 MB/see, the system already runs close to the limits of practical data collection and storage.
After collection, the point cloud data files must usually be processed and spatially indexed for efficient use and ability to visualize the collected data. Since the data generally is acquired in a two-dimensional (“2D”) grid, the data is generally stored in 2D grid order (allowing for some spaces that occur when an emitted laser pulse is never reflected back to the system and collected). To look at all the data in 3D generally requires several days to index the data in 3D on a high-end desktop PC for a day's collection of points. As such, this format conversion generally takes significantly longer than the collection time. This conversion is necessary for most uses of scan data since it is typical to combine data from multiple positions to represent the scanned scene. In this usage, the 2D scan formats are practically of no use.